package code;


public class StockIV {
	
	public int easyMaxProfit(int[] prices){
		int ans=0;
		for(int i=1;i<prices.length;i++){
			if(prices[i]>prices[i-1])
				ans+=prices[i]-prices[i-1];
		}
		return ans;
		
	}
	public int maxProfit(int kk,int[] prices){
		int ans=0;
		
		int days=prices.length;
		/*
		 * 设计transaction的状态
		 * 一次交易分割成一次买和一次卖的过程
		 * 
		 * 奇数次的时候，把买的操作，当成掏钱的过程，使得结果-price
		 * 偶数次的时候，把卖的操作,当成是收益，+price
		 * 把原来的问题变成了：2*kk加入背包的过程。
		 */
		int maxTransactions=2*kk>days?days:2*kk;
		//无次数限制的买与卖
		if(maxTransactions>=days) 
			return easyMaxProfit(prices);
		
		int[] dp=new int[maxTransactions+1];
		int i,j,k;
		for(i=0;i<=maxTransactions;i++)
			dp[i]=0;
		
		for(i=0;i<days;i++){
			k=2*kk>i+1?i+1:2*kk;
			for(j=1;j<=k;j++){
				int factor;
				if(j%2==1)	factor=-1;
				else factor=1;
				if(dp[j]<dp[j-1]+factor*prices[i])
					dp[j]=dp[j-1]+factor*prices[i];
			}
		}
		for(i=0;i<=maxTransactions;i++){
			if(ans<dp[i])	ans=dp[i];
			System.out.println(i+"   "+dp[i]);
		}
		return ans;
	}
	public static void main(String[] args){
		StockIV stock=new StockIV();
		int[] prices={2,1,2,0,1};
		int ans=stock.maxProfit(2, prices);
		System.out.println(ans);
	}
}
